/**
 * 494. 目标和
 * https://leetcode-cn.com/problems/target-sum/
 */

// /**
//  * @param {number} target
//  * @param {number[]} nums
//  * @param {number} begin
//  * @param {Map<number, number>[]} cache
//  * @return {number}
//  */
// function subTargetSumWays(target, nums, begin, cache) {
//   if (cache[begin].has(target)) {
//     return cache[begin].get(target);
//   }
//   let sum = 0;
//   const num = nums[begin];
//   if (begin === nums.length - 1) {
//     sum += (num === target ? 1 : 0);
//     sum += (num === -target ? 1 : 0);
//   } else {
//     sum += subTargetSumWays(target - num, nums, begin + 1, cache);
//     sum += subTargetSumWays(target + num, nums, begin + 1, cache);
//   }
//   cache[begin].set(target, sum);
//   return sum;
// }
//
// /**
//  * @param {number[]} nums
//  * @param {number} target
//  * @return {number}
//  */
// function findTargetSumWays(nums, target) {
//   const cache = new Array(nums.length);
//   for (let i = 0; i < cache.length; i += 1) {
//     cache[i] = new Map();
//   }
//   return subTargetSumWays(target, nums, 0, cache);
// }

/**
 * 动态规划
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function findTargetSumWays(nums, target) {
  let sum = 0;
  for (let i = 0; i < nums.length; i += 1) {
    sum += nums[i];
  }
  if (target > sum || ((sum - target) & 1) !== 0) {
    return 0;
  }
  const neg = (sum - target) >> 1;
  const dp = new Array(nums.length + 1);
  for (let i = 0; i <= nums.length; i += 1) {
    dp[i] = new Array(neg + 1).fill(0);
  }
  dp[0][0] = 1;
  let num;
  for (let i = 1; i <= nums.length; i += 1) {
    num = nums[i - 1];
    for (let j = 0; j <= neg; j += 1) {
      if (num > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
      }
    }
  }
  return dp[nums.length][neg];
}

console.log(findTargetSumWays([1, 1, 1, 1, 1], 3) === 5);
console.log(findTargetSumWays([1], 1) === 1);
console.log(findTargetSumWays([1, 0], 1) === 2);
console.log(findTargetSumWays([2, 107, 109, 113, 127, 131, 137, 3, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 47, 53], 1000) === 0);
